
public class Test32 {
    public static int numberOfBetween1AndN(int n){
        if (n<=0) return 0;
        String value = n+"";
        int[] numbers = new int[value.length()];
        for (int i = 0; i< value.length();i++){
            numbers[i] = value.charAt(i) -'0';
        }
        return numberOf1(numbers,0);
    }
    public static int numberOf1(int[] numbers,int curId){
        if (numbers == null || curId >= numbers.length || curId < 0) return 0;
        int first = numbers[curId];//第一个数数字
        int length = numbers.length-curId;
        if (length == 1 &&first == 0) return 0;
        if (length == 1 && first == 1) return 1;
        int numFirstDigit = 0;
        if (first > 1) numFirstDigit = PowerBase10(length-1);
        else if (first == 1) numFirstDigit = auti(numbers,curId+1) +1;
        int numOtherDigit = first*(length-1) * PowerBase10(length-2);
        int numRecurise = numberOf1(numbers,curId+1);
        return numFirstDigit + numOtherDigit + numRecurise;

    }

    /**
     * 转换为整数
     * @param numbers
     * @param i
     * @return
     */
    public static int auti(int[] numbers,int i){
        int res = 0;
        for (int j = i;j<numbers.length;j++){
            res = res*10 + numbers[j];
        }
        return res;
    }

    /**
     * 10^n次幂
     * @param n
     * @return
     */
    public static int PowerBase10(int n){
        int resule = 1;
        for (int i =0;i<n;i++){
            resule *= 10;
        }
        return resule;
    }

    public static void main(String[] args) {
        System.out.println(numberOfBetween1AndN(10000)); // 4001
        System.out.println(numberOfBetween1AndN(21345)); // 18821
    }
}
